#include <iostream> //非递归实现前中后序遍历
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
struct Treenode
{
    int data;
    Treenode *parent, *left, *right;
};
Treenode *root = NULL;
Treenode *dic_node[1000];
bool is_come[1000];
Treenode *node_insert(int now, int le, int ri)
{
    if (dic_node[now] == NULL)
    {
        Treenode *temp = new Treenode;
        temp->data = now;
        temp->left = NULL;
        temp->right = NULL;
        dic_node[now] = temp;
    }
    if (le != -1)
    {
        if (dic_node[le] == NULL)
        {
            Treenode *temp = new Treenode;
            temp->data = le;
            temp->left = NULL;
            temp->right = NULL;
            dic_node[le] = temp;
        }
        dic_node[now]->left = dic_node[le];
        dic_node[le]->parent = dic_node[now];
    }
    if (ri != -1)
    {
        if (dic_node[ri] == NULL)
        {
            Treenode *temp = new Treenode;
            temp->data = ri;
            temp->left = NULL;
            temp->right = NULL;
            dic_node[ri] = temp;
        }
        dic_node[now]->right = dic_node[ri];
        dic_node[ri]->parent = dic_node[now];
    }
    return dic_node[now];
}

void pre1_traversal(Treenode *root)
{
    // 使用非递归的方式实现先序遍历
    if (root == NULL)
        return;
    stack<Treenode *> s;
    s.push(root);
    while (!s.empty())
    {
        cout << s.top()->data << ' ';
        Treenode *temp = s.top();
        s.pop();
        if (temp->right != NULL)
            s.push(temp->right);
        if (temp->left != NULL)
            s.push(temp->left);
    }
    return;
}
void in1_traversal(Treenode *root)
{
    // 使用非递归的方式实现中序遍历
    if (root == NULL)
        return;
    stack<Treenode *> s;
    s.push(root);
    // Treenode *temp=root;
    memset(is_come, 0, sizeof(is_come));
    // is_come[root->data]=true;
    while (!s.empty())
    {
        Treenode *temp = s.top();
        if (!is_come[temp->data])
        {
            if (temp->left != NULL)
                s.push(temp->left);
            is_come[temp->data] = true;
        }
        else
        {
            cout << temp->data << ' ';
            s.pop();
            if (temp->right != NULL)
                s.push(temp->right);
        }
    }
}
void post1_traversal(Treenode *root)
{
    if (root == NULL)
        return;
    stack<Treenode *> s;
    s.push(root);
    memset(is_come, 0, sizeof(is_come));
    while (!s.empty())
    {
        Treenode *temp = s.top();
        if (!is_come[temp->data])
        {
            if (temp->right != NULL)
                s.push(temp->right);
            if (temp->left != NULL)
                s.push(temp->left);
            is_come[temp->data] = true;
        }
        else
        {
            cout << temp->data << ' ';
            s.pop();
        }
    }
}
int main()
{
    int n;
    cin >> n;
    int now, le, ri;
    for (int i = 1; i <= n; i++)
    {
        cin >> now >> le >> ri;
        if (i == 1)
            root = node_insert(now, le, ri);
        else
            node_insert(now, le, ri);
    }
    pre1_traversal(root);
    cout << endl;
    in1_traversal(root);
    cout << endl;
    post1_traversal(root);
    cout << endl;
    return 0;
}